<!DOCTYPE html>
<html lang=en-US class="noScroll">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge">

        <title>Finite Graph</title>

        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/fonts.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/links.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/search.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/mathJax.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/darkMode.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/variables.css">
        <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/noProperty.css">

        <script src="https://cdn.jsdelivr.net/npm/fuse.js/dist/fuse.js"></script>

        <script src="https://zhaoshenzhai.github.io/mathwiki/js/input.js" type="module"></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/search.js" type="module"></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/mathJax.js" type="module" async></script>
        <script src="https://zhaoshenzhai.github.io/mathwiki/js/darkMode.js" type="module"></script>

        <div style="display:none;" id="preamble"></div>
    </head>

    <body class="listenDark">
        
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/metaLinks.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/metaTOC.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/preview.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/expand.js" type="module"></script>
    <script src="https://zhaoshenzhai.github.io/mathwiki/js/single/side.js" type="module"></script>

    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/ctrlButtons.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/collapsible.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/metadata.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/preview.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/single.css">
    <link rel="stylesheet" href="https://zhaoshenzhai.github.io/mathwiki/css/env.css">

    <div id="mainPage">
        <button id="toggleDark" onclick="toggleDark(document, false, true, true);" class="ctrlButton noSelect inPreview">
            <img id="toggleDarkIcon" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/sun.svg">
        </button>
        <button id="toggleSide" onclick="toggleSide(false);" class="ctrlButton noSelect inPreview">
            <img id="toggleSideIcon" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/sun.svg">
        </button>
        <div id="content" class="left noScroll">
            
                <h1 id="title" titleSize="">
                    Finite Graph
                </h1>
            
            <p>Let $G$ be a (simple) <a href=https://zhaoshenzhai.github.io/mathwiki/graph.md class="internalLink references" title="Graph" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/graph.md&#34;, {&#34;Date&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Graph&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Graph&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/graph.md&#34;, {&#34;Date&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T18:13:24-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Graph&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">graph</a>. The condition that $V(G)$ be finite allows us to apply methods from finite combinatorics to analyze $G$. We give some graph-theoretic frameworks for which such combinatorics applies to. Ultimately, these arguments boil down to applying the Pigeonhole Principle, or using the fact that $\N$ is <a href=https://zhaoshenzhai.github.io/mathwiki/well_order.md class="internalLink references ghostLink" title="well-ordered" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/well_order.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/well_order.md&#34;, &#34;nopPage&#34;);">well-ordered</a>.</p>
<br>
<p>  However, certain results from finite graph theory have more elegant proofs if we are willing to use techniques involving <a href=https://zhaoshenzhai.github.io/mathwiki/infinite_graph.md class="internalLink references ghostLink" title="infinite" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/infinite_graph.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/infinite_graph.md&#34;, &#34;nopPage&#34;);">infinite</a> graphs, and in some cases, those are the <em>only</em> known proofs. The prototypical example of this bridge is <em><a href=https://zhaoshenzhai.github.io/mathwiki/ramseys_theorem class="internalLink properties ghostLink" title="Ramsey’s Theorem" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/ramseys_theorem&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/ramseys_theorem&#34;, &#34;nopPage&#34;);">Ramsey’s Theorem</a></em>.</p>
<div class="space"></div>
<p>  <em>Throughout this entire page, all graphs are finite unless stated otherwise.</em></p>
<h2 id="basic-notions">Basic Notions</h2>
<p>The <em><a href=https://zhaoshenzhai.github.io/mathwiki/degree_graph.md class="internalLink constructions" title="Degree (Graph Theory)" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/degree_graph.md&#34;, {&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/degree_graph.md&#34;, {&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">degree</a></em> $d_G(v)$ of a vertex $v\in V$ is the cardinality of its <em>neighbors</em> $N_G(v)\coloneqq\l\{u\in V\st uv\in E\r\}$. It can easily be shown<a href=https://zhaoshenzhai.github.io/mathwiki/degree_graph.md/#handshaking_lemma class="internalLink properties dag" title="Degree (Graph Theory)" mathLink="" secID="handshaking_lemma" secDisplay="Handshaking Lemma" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/degree_graph.md/#handshaking_lemma&#34;, {&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/degree_graph.md/#handshaking_lemma&#34;, {&#34;Date&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-06T20:21:22-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Degree (Graph Theory)&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/degree_graph&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">$^\dagger$</a> that $\sum_{v\in V}d_G(v)=2|E(G)|$, which implies that the number of vertices of odd degree is even. Control over the minimum degree $\delta(G)$, maximum degree $\Delta(G)$, or the average degree $d(G)$ can provide some rough bounds of sizes of certain subgraphs of $G$.</p>
<br>
<p>  A simple example of this is that every graph contains a <a href=https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md/#paths_and_walks class="internalLink references" title="Connectivity in Graphs" mathLink="" secID="paths_and_walks" secDisplay="Paths and Walks" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md/#paths_and_walks&#34;, {&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md/#paths_and_walks&#34;, {&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">path</a> of length $\delta(G)$ and, if $\delta(G)\geq2$, a cycle of length at least $\delta(G)+1$.</p>
<blockquote>
<div class="collapsibleContainer" id=""><i class="proofHeader collapsibleHeaderButton collapsibleHeader noSelect">Proof.</i><span class="collapsibleHintText noSelect"><i> Click to expand...</i></span>

        <span class="collapsibleContent">Let $P\coloneqq v_0\cdots v_k$ be a path of maximum length. The neighbors $N_G(v_0)$ must all lie on $P$, by maximality of $k$, and hence we have $k\geq d_G(v_0)\geq\delta(G)$. Moreover, if $i&gt;0$ is the maximal index for which $v_0v_i\in E$, then $i\geq d_G(v_0)\geq\delta(G)$, and hence $v_0\cdots v_iv_0$ is a cycle of length $i+1\geq\delta(G)+1$.<span style="float:right;">$\blacksquare$</span></span></div>

</blockquote>
<h1 id="basic-questions-and-results">Basic Questions and Results</h1>
<p>The first ever result in graph theory is the <em>Königsberg Bridge Problem</em>, solved by Euler in 1736, which concerns walks in a graph that traverse every edge exactly once. Nowadays, they are called <em>Euler tours</em>, and graphs that admit such tours are said to be <em>Eulerian</em>.</p>
<div class="env" id=""><img class="icon noSelect listenDark" src="https://zhaoshenzhai.github.io/mathwiki/css/fa/theorem.svg"><b class="envTitle">Theorem (Königsberg Bridge; Euler 1736). </b>A connected graph is Eulerian iff every vertex has even degree.</div>

<div class="collapsibleContainer" id=""><i class="proofHeader collapsibleHeaderButton collapsibleHeader noSelect">Proof.</i><span class="collapsibleHintText noSelect"><i> Click to expand...</i></span>

        <span class="collapsibleContent">Let $G$ be a connected graph. If an Euler tour exists and a vertex $v\in V(G)$ appears $k$ times in this tour, then $d_G(v)=2k$ is even. Conversely, we proceed by induction on $l\coloneqq|E(G)|$. The case when $l=0$ is immediate, so suppose that $l&gt;0$.</span></div>

<h2 id="hahahugoshortcode23s10hbhb"><a href=https://zhaoshenzhai.github.io/mathwiki/hamiltonian_cycle.md class="internalLink constructions ghostLink" title="Hamiltonian Cycle" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/hamiltonian_cycle.md&#34;, &#34;nopPage&#34;);" onmouseleave="clearPreviewSide(&#34;nopPage&#34;);" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/hamiltonian_cycle.md&#34;, &#34;nopPage&#34;);">Hamiltonian Cycle</a></h2>
<p><span style="color:red"><strong>TODO</strong>.</span></p>
<p>A basic result illustrating this phenomenon is that every <a href=https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md class="internalLink references" title="Connectivity in Graphs" mathLink="" secID="" secDisplay="" onmouseover="previewSide(&#34;https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md&#34;, {&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onmouseleave="clearPreviewSide({&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});" onclick="updateCurrentSide(event, &#34;https://zhaoshenzhai.github.io/mathwiki/connectivity_graphs.md&#34;, {&#34;Date&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;Lastmod&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;PublishDate&#34;:&#34;2024-09-05T22:37:16-04:00&#34;,&#34;ExpiryDate&#34;:&#34;0001-01-01T00:00:00Z&#34;,&#34;Aliases&#34;:null,&#34;BundleType&#34;:&#34;&#34;,&#34;Description&#34;:&#34;&#34;,&#34;Draft&#34;:false,&#34;IsHome&#34;:false,&#34;Keywords&#34;:null,&#34;Kind&#34;:&#34;page&#34;,&#34;Layout&#34;:&#34;&#34;,&#34;LinkTitle&#34;:&#34;Connectivity in Graphs&#34;,&#34;IsNode&#34;:false,&#34;IsPage&#34;:true,&#34;Path&#34;:&#34;/connectivity_graphs&#34;,&#34;Slug&#34;:&#34;&#34;,&#34;Lang&#34;:&#34;en&#34;,&#34;IsSection&#34;:false,&#34;Section&#34;:&#34;&#34;,&#34;Sitemap&#34;:{&#34;ChangeFreq&#34;:&#34;&#34;,&#34;Priority&#34;:-1,&#34;Filename&#34;:&#34;sitemap.xml&#34;,&#34;Disable&#34;:false},&#34;Type&#34;:&#34;page&#34;,&#34;Weight&#34;:0});">connected</a> graph with $|V|\geq3$ contains path or cycle of length at least $\min\l\{2\delta(G),|V|\r\}$. In particular, this implies <em>Dirac’s Theorem</em>, that $G$ contains a Hamiltonian cycle if $2\delta(G)\geq|V|\geq3$.</p>
<div class="space"></div>
<div class="collapsibleContainer" id=""><i class="proofHeader collapsibleHeaderButton collapsibleHeader noSelect">Proof.</i><span class="collapsibleHintText noSelect"><i> Click to expand...</i></span>

        <span class="collapsibleContent"><p>Let $n\coloneqq|V|$. Dirac’s Theorem follows from the claim, since if $2\delta(G)\geq n$, then $G$ is connected: otherwise any vertex $v$ in its smallest component $C$ has degree less than $|C|\leq n/2$. Since $G$ cannot contain a path of length $n$, it must contain a cycle of length at least $n$, whence a Hamiltonian cycle.</p>
<br>
<p>  To prove the claim, suppose that there is no path of length $\min\l\{2\delta(G),n\r\}$. Let $P\coloneqq v_0\cdots v_k$ be the longest path, so $k&lt;2\delta(G)$. By maximality of $k$, the neighbors of $v_0$ must lie on ‘right ends’ $v_{i+1}$ of edges $v_iv_{i+1}\in E(P)$; similarly, neighbors of $v_k$ must lie on ‘left ends’ of edges in $P$. But since $\delta(G)&gt;k/2$, there must be some edge $v_iv_{i+1}\in E(P)$ such that $C\coloneqq v_0v_{i+1}Pv_kv_iPv_0$ is a cycle, which has length $k+1$. We claim that $C$ is as desired, by showing that it is Hamiltonian.</p>
<br>
<p>  If not, then by connectedness of $G$ there is some $v\in G-C$ neighboring a vertex $v_j\in V(P)$. Cutting any incident edge of $v_j$ in $C$ and adding an edge $vv_j$ will result in a path of length $k+1$, contradicting the choice of $P$.<span style="float:right;">$\blacksquare$</span></p>
</span></div>

<h2 id="matchings-and-coverings">Matchings and Coverings</h2>
<h2 id="flows-and-colourings">Flows and Colourings</h2>
<h2 id="planar-graphs">Planar Graphs</h2>
<h1 id="compactness-and-contradiction">Compactness and Contradiction</h1>


            <div class="bottomSpace">&nbsp;</div>
        </div>

        <div id="side" class="inPreview">
            <div id="metadata" class="right noScroll">
                September 6, 2024 | Zhaoshen Zhai

                <div>References:
                     None 
                </div>
                <div>Tags:
                    
                        <div class="metaButton metaTag listenDark">#In_Progress</div>
                    
                </div>
                <br>

                <div>Table of Contents:
                    <button class="metaButton listenDark" onclick="showMetaTOC();">Show</button>
                    <button class="metaButton listenDark" onclick="hideMetaTOC();">Hide</button>
                    <div id="metaTOC"></div>
                </div>
                <div>Links:
                    <button class="metaButton listenDark" onclick="expandMetaLinks();">Expand</button>
                    <button class="metaButton listenDark" onclick="collapseMetaLinks();">Collapse</button>
                    <div id="metaLinks"></div>
                </div>

                <div class="bottomSpace">&nbsp;</div>
            </div>
            <div id="previewContainer">
                <button id="resetSide" onclick="resetSide();" class="ctrlButton noSelect" style="display: none;">
                    <img src="https://zhaoshenzhai.github.io/mathwiki/css/fa/close.svg">
                </button>
            </div>
        </div>
    </div>


        <div id="searchBox" style="display: none;">
            <input id="searchBar" placeholder="Search for a note..." onkeydown="search(event);">
            <ul id="searchList" onclick="searchOpen(getCtrlKeyDown());">
                <li id="searchItem0" onmouseover="searchItemActive(0)"></li>
                <li id="searchItem1" onmouseover="searchItemActive(1)"></li>
                <li id="searchItem2" onmouseover="searchItemActive(2)"></li>
                <li id="searchItem3" onmouseover="searchItemActive(3)"></li>
                <li id="searchItem4" onmouseover="searchItemActive(4)"></li>
                <li id="searchItem5" onmouseover="searchItemActive(5)"></li>
                <li id="searchItem6" onmouseover="searchItemActive(6)"></li>
                <li id="searchItem7" onmouseover="searchItemActive(7)"></li>
                <li id="searchItem8" onmouseover="searchItemActive(8)"></li>
                <li id="searchItem9" onmouseover="searchItemActive(9)"></li>
            </ul>
        </div>
    </body>
</html>
